//Cracking coding interview 17.6
//find string segments
//1:29PM--1:57PM--2:05PM(bugfree)

#include<vector>
using namespace std;



void SegList(vector<int>& inputvec, int &pos0, int &pos1) {
	if (inputvec.empty()) {
		pos0=-1;
		pos1=-1;
		return;
	}

	vector<int> vec1;
	vec1.reserve(inputvec.size());
	bool fnd=false;
	for (int i=0; i<inputvec.size(); i++) {
		if(!fnd && (i==0 || inputvec[i-1]<=inputvec[i])) {
			vec1.push_back(inputvec[i]);
		} else {
			int pos=i;
			int j;
			for(j=vec1.size()-1; j>=0; j--) {
				if(vec1[j]>inputvec[i]) {
					vec1.pop_back();
				}
			}
			fnd=true;
		}
	}

	pos0=vec1.size();

	vec1.clear();
	fnd=false;
	for (int i=inputvec.size()-1; i>=0; i--) {
		if(!fnd && (i==0 || inputvec[i-1]<=inputvec[i])) {
			vec1.push_back(inputvec[i]);
		} else {
			int pos=i;
			int j;
			for(j=vec1.size()-1; j>=0; j--) {
				if(vec1[j]<inputvec[i]) {
					vec1.pop_back();
				}
			}
			fnd=true;
		}
	}

	pos1=inputvec.size()-vec1.size()-1;
}

int main(int argc, char *argv[]) {
	int input[13]={1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19};
	vector<int> inputVec(input, input+13);
	int pos0, pos1;
	SegList(inputVec, pos0, pos1);
}